class ListNode {
    constructor(key, val) {
        this.val = val
        this.key = key
        this.next = null
        this.pre = null
    }
}
class LRUCache {
    constructor(capacity) {
        this.map = new Map()
        this.capacity = capacity
        this.dummy = new ListNode()
    }
    get(key) {
        let node = this.getNode(key)
        return node ? node.val : -1
    }
    put(key, value) {
        let node = this.getNode(key)
        if(node) {
            node.val = value
            return
        }
        node = new ListNode(key, value)
        this.map.set(key, node)
        this.pushFront(node)
        if(this.map.size > this.capacity) { // 容量达到最大值
            const backNode = this.dummy.pre // 拿到最久未使用的节点
            this.map.delete(backNode.key) // 删除该节点
            this.remove(backNode)
        }
    }
    pushFront(node) {
        node.pre = this.dummy
        node.next = this.dummy.next
        node.next.pre = node
        node.pre.next = node
    }
    remove(node) {
        node.pre.next = node.next
        node.next.pre = node.pre
    }
    getNode(key) { // 更新节点访问时间，即将节点放到双向链表的开头
        if(!this.map.has(key)) return null
        const node = this.map.get(key)
        // 更新节点
        this.remove(node)
        this.pushFront(node)
    }
}